| 翻訳と辞書 |
| Speedup theorem ： ウィキペディア英語版 |
Speedup theorem
In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a more efficient algorithm solving the same problem. It may refer to:
*Linear speedup theorem, that the space and time requirements of a Turing machine solving a decision problem can be reduced by a multiplicative constant factor.
*Blum's speedup theorem, which provides speedup by any computable function (not just linear, as in the previous theorem).
It may also refer to:
*Gödel's speed-up theorem, showing that some mathematical proofs can be drastically shortened in stronger axiom systems
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Speedup theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|